package pro.softzhang.algo.lc500;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
public class LC547_NumberOfProvinces {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public int findCircleNum(int[][] isConnected) {
            boolean[] visited = new boolean[isConnected.length];
            int r = 0;
            for (int i = 0; i < isConnected.length; i++) {
                if (!visited[i]) {
                    doFindCircleNum(isConnected, visited, i);
                    r++;
                }
            }
            return r;
        }

        private void doFindCircleNum(int[][] isConnected, boolean[] visited, int i) {
            Queue<Integer> q = new LinkedList<>();
            q.add(i);
            visited[i] = true;
            while (!q.isEmpty()) {
                int t = q.remove();
                for (int friend = 0; friend < isConnected.length; friend++) {
                    if (isConnected[t][friend] == 1 && !visited[friend]) {
                        q.add(friend);
                        visited[friend] = true;
                    }
                }
            }
        }
    }

    static
    class Solution1 {
        public int findCircleNum(int[][] isConnected) {
            int cities = isConnected.length, provinces = 0;
            boolean[] visited = new boolean[cities];
            for(int i = 0; i < cities; i++) {
                if (!visited[i]) {
                    dfs(isConnected, visited, cities, i);
                    provinces++;
                }
            }
            return provinces;
        }

        private void dfs(int[][] isConnected, boolean[] visited, int cities, int i) {
            for(int j = 0; j < cities; j++) {
                if (isConnected[i][j] == 1 && !visited[j]) {
                    visited[j] = true;
                    dfs(isConnected, visited, cities, j);
                }
            }
        }
    }
}
